// coding: utf-8
// @Author : lryself
// @Date : 2020/10/23 22:44
// @Software: GoLand

package main

import "sort"

func main() {
	
}


type ListNode struct {
	Val int
	Next *ListNode
}

func insertionSortList(head *ListNode) *ListNode {
	if head == nil{
		return nil
	}
	if head.Next == nil{
		return head
	}
	intlist := []int{head.Val}
	p := head.Next
	for p != nil{
		intlist = append(intlist, p.Val)
		p = p.Next
	}
	sort.Ints(intlist)
	result := &ListNode{}
	p = result
	for _,i := range intlist{
		p.Next = &ListNode{Val: i}
		p = p.Next
	}
	return result.Next
}